#include "BigInteger.h"

/**
 * 有参构造函数
 * @param num int转大数，但超过int范围的请传入string num参数进行构造
*/
BigInteger::BigInteger(int num){
    this->arr = std::to_string(num);
    size_t i = 0;
    if (!arr.empty() && arr[0] == '-') i = 1;
    while (i < arr.size()) {
        if (arr[i] == '0') arr.erase(i, 1);
        else break;
    }
    if (arr.empty() || arr == "-") arr = "0";
    this->length = arr.size();
}

/**
 * 有参构造函数
 * @param num 使用string模拟数字参数进行构造
*/
BigInteger::BigInteger(std::string num){
    this->arr = num;
    size_t i = 0;
    if (!arr.empty() && arr[0] == '-') i = 1;
    while (i < arr.size()) {
        if (arr[i] == '0') arr.erase(i, 1);
        else break;
    }
    if (arr.empty() || arr == "-") arr = "0";
    this->length = arr.size();
}

/**
 * 无参构造，默认为0
*/
BigInteger::BigInteger(){
    this->arr.resize(1,'0');
    this->length = 1;
}

/**
 * 获取大数数值
 * @return this->arr：获取当前值
*/
std::string BigInteger::getValue(){
    return this->arr;
}

/**
 * 修改大数数值
 * @param num 通过字符串形式数组修改大数
*/
void BigInteger::setValue(std::string num){
    this->arr.clear();
    this->arr = num;
    size_t i = 0;
    if (!arr.empty() && arr[0] == '-') i = 1;
    while (i < arr.size()) {
        if (arr[i] == '0') arr.erase(i, 1);
        else break;
    }
    if (arr.empty() || arr == "-") arr = "0";
    this->length = arr.size();
}

/**
 * 双目运算，比较大小，检查左边是否小于右边
 * @param *this lvalue @param args rvalue
*/
const bool BigInteger::operator< (const BigInteger& args) const{ //比较大小，看哪一方小
    // 比较符号
    if (this->arr.empty() || args.arr.empty()) return false;
    
    // 处理符号差异
    if (this->arr[0] != '-' && args.arr[0] == '-') return false;
    if (this->arr[0] == '-' && args.arr[0] != '-') return true;
    
    // 同为正数
    if (this->arr[0] != '-' && args.arr[0] != '-') {
        if (this->arr.length() < args.arr.length()) return true;
        if (this->arr.length() > args.arr.length()) return false;
        
        // 长度相等时逐位比较
        for (size_t i = 0; i < arr.length(); i++) {
            if (this->arr[i] < args.arr[i]) return true;
            if (this->arr[i] > args.arr[i]) return false;
        }
        return false;  // 相等时返回false
    }
    
    // 同为负数
    if (this->arr.length() > args.arr.length()) return true;
    if (this->arr.length() < args.arr.length()) return false;
    
    // 长度相等且为负时，绝对值大的反而小
    for (size_t i = 0; i < arr.length(); i++) {
        if (this->arr[i] < args.arr[i]) return true;
        if (this->arr[i] > args.arr[i]) return false;
    }
    return false;  // 相等时返回false
}

/**
 * 比较大小，返回较大的一方
 * @param X 参数1 @param Y 参数2
 * @return 返回较大的一方
*/
BigInteger BigInteger::max(BigInteger X, BigInteger Y){ //max函数
    BigInteger result = X > Y ? X : Y;
    return result;
}

/**
 * 比较大小，返回较小的一方
 * @param X 参数1 @param Y 参数2
 * @return 返回较小的一方
*/
BigInteger BigInteger::min(BigInteger X, BigInteger Y){ //min函数
    return X < Y ? X : Y;
}

/**
 * 双目运算，比较大小，检查左边是否大于右边
 * @param *this lvalue @param args rvalue
*/
const bool BigInteger::operator> (const BigInteger& args) const{
    // 处理特殊情况（空字符串）
    if (arr.empty() || args.arr.empty()) return false;
    
    // 处理符号差异
    if (arr[0] != '-' && args.arr[0] == '-') return true;  // 正 > 负
    if (arr[0] == '-' && args.arr[0] != '-') return false; // 负 < 正
    
    // 同为正数的情况
    if (arr[0] != '-' && args.arr[0] != '-') {
        // 比较位数
        if (arr.length() > args.arr.length()) return true;
        if (arr.length() < args.arr.length()) return false;
        
        // 位数相等时逐位比较
        for (size_t i = 0; i < arr.length(); i++) {
            if (arr[i] > args.arr[i]) return true;
            if (arr[i] < args.arr[i]) return false;
        }
        return false;  // 相等时返回false
    }
    
    // 同为负数的情况（符号相同）
    // 比较位数
    if (arr.length() > args.arr.length()) return false;  // 负数的位数越多值越小
    if (arr.length() < args.arr.length()) return true;   // 负数的位数越少值越大
    
    // 位数相等时逐位比较
    for (size_t i = 0; i < arr.length(); i++) {
        if (arr[i] > args.arr[i]) return false;  // 负数的某位越大，实际值越小
        if (arr[i] < args.arr[i]) return true;    // 负数的某位越小，实际值越大
    }
    return false;  // 相等时返回false
}

/**
 * 赋值运算
 * @param this lvalue @param args rvalue
 * 
 * 把右值赋值给左值
*/
void BigInteger::operator= (const std::string args) {
    for (size_t i = 0; i < args.size(); i++)
        if(args[i] < '0' || args[i] > '9'){
            this->arr = "0";
            break;
    }
    this->arr = args;
} //数字赋值

/**
 * 双目运算，判断二者是否相等
 * @param this lvalue @param args rvalue
 * @return 如果相等则返回true，否则返回false
*/
const bool BigInteger::operator== (const BigInteger& args) const{
    if((this->arr[0] != '-' && args.arr[0] == '-') || (this->arr[0] == '-' && args.arr[0] != '-') || (this->arr.size() != args.arr.size())) return false;
    else {
        for(size_t i = 0; i < this->length; i++) if(this->arr[i] != args.arr[i]) return false;
        return true; 
    }
} //比较二者是否相等

/** 
 * 获取当前大数的绝对值
 * @return BigInteger对象
*/
BigInteger BigInteger::abs() const {
    if (this->arr[0] == '-') {
        return BigInteger(this->arr.substr(1));
    }
    return *this;
}

/**
 * 双目运算，判断左值是否小于相等右值
 * @param this lvalue @param args rvalue
 * 如果小于等于则返回true，否则返回false
*/
const bool BigInteger::operator<= (const BigInteger& other) const {
    if (*this == other) return true;
    return *this < other;
}

/**
 * 双目运算，判断左值是否大于相等右值
 * @param this lvalue @param args rvalue
 * 如果大于等于则返回true，否则返回false
*/
const bool BigInteger::operator>= (const BigInteger& other) const {
    if (*this == other) return true;
    return *this > other;
}

std::ostream& operator<<(std::ostream& os, const BigInteger& data) {
    os << data.arr;
    return os;
} //cout输出重载

std::istream& operator>>(std::istream& is, BigInteger& data) {
    std::string temp;
    is >> temp;
    BigInteger trans(temp);
    data.arr = trans.arr;
    return is;
} //cin输出符号重载

/**
 * 无符号加法
 * @param a 参数1 @param b 参数2
 * 通过倒序相加按位进一
 * @return 得到BigInteger对象
*/
inline std::string BigInteger::unsigned_add(std::string a, std::string b) const{
    std::string res;
    int carry = 0;
    int i = a.size() - 1, j = b.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int n1 = (i >= 0) ? a[i--] - '0' : 0;
        int n2 = (j >= 0) ? b[j--] - '0' : 0;
        int sum = n1 + n2 + carry;
        carry = sum / 10;
        res.insert(res.begin(), '0' + (sum % 10));
    }
    return res;
}

/**
 * 无符号减法（要求a>=b）
 * @param a 参数1 @param b 参数2
 * 通过倒序相加按位进一
 * @return 得到BigInteger对象
*/
inline std::string BigInteger::unsigned_sub(std::string a, std::string b) const{
    std::string res;
    int borrow = 0;
    int i = a.size() - 1, j = b.size() - 1;
    while (i >= 0) {
        int n1 = (a[i--] - '0') - borrow; //借10减1
        int n2 = (j >= 0) ? b[j--] - '0' : 0;
        borrow = 0;
        if (n1 < n2) {
            n1 += 10;
            borrow = 1; //借10标记下一位数减去1
        }
        res.insert(res.begin(), '0' + (n1 - n2));
    }
    // 移除前导零
    size_t pos = res.find_first_not_of('0');
    if (pos != std::string::npos) res = res.substr(pos);
    else res = "0";
    return res;
}

// 辅助函数：比较无符号字符串
inline int BigInteger::compare_unsigned(const std::string& a, const std::string& b) const{
    if (a.length() != b.length())
        return a.length() > b.length() ? 1 : -1;
    for (size_t i = 0; i < a.length(); i++) {
        if (a[i] != b[i])
            return a[i] > b[i] ? 1 : -1;
    }
    return 0;
}

/**
 * 双目运算，判断左值是否不等于相等右值
 * @param this lvalue @param args rvalue
 * @return 如果不等于则返回true，否则返回false
*/
const bool BigInteger::operator!= (const BigInteger& args) const {
    return !(*this == args);
}

/**
 * 双目运算，二者相加
 * @param this lvalue @param args rvalue
 * @return 相加结果
*/
const BigInteger BigInteger::operator+ (const BigInteger& args) const{
    std::string num1 = this->arr;
    std::string num2 = args.arr; //读取数据

    bool neg1 = (num1[0] == '-');
    bool neg2 = (num2[0] == '-'); //判断正负数
    std::string abs1 = neg1 ? num1.substr(1) : num1;
    std::string abs2 = neg2 ? num2.substr(1) : num2;

    // 处理同号情况
    if (neg1 == neg2) {
        std::string res_str = unsigned_add(abs1, abs2);
        if (neg1 && res_str != "0") res_str = "-" + res_str;
        return BigInteger(res_str);
    }

    // 处理异号情况
    int cmp = compare_unsigned(abs1, abs2);
    if (cmp == 0) return BigInteger("0");  // 绝对值相等时结果为0

    std::string res_str;
    if (cmp > 0) {  // |this| > |args|
        res_str = unsigned_sub(abs1, abs2);
        if (neg1) res_str = "-" + res_str;  // this为负数，结果为负
    } else {        // |this| < |args|
        res_str = unsigned_sub(abs2, abs1);
        if (neg2) res_str = "-" + res_str;  // args为负数，结果为负
    }

    return BigInteger(res_str);
}

/**
 * 双目运算，二者相减
 * @param this lvalue @param args rvalue
 * @return 相减结果
*/
const BigInteger BigInteger::operator- (const BigInteger& args) const{
    std::string num1 = this->arr;
    std::string num2 = args.arr; //读取数据

    bool neg1 = (num1[0] == '-');
    bool neg2 = (num2[0] == '-'); //判断正负数
    std::string abs1 = neg1 ? num1.substr(1) : num1;
    std::string abs2 = neg2 ? num2.substr(1) : num2;

    // 处理四种符号组合情况
    int cmp = compare_unsigned(abs1, abs2);

    // 1. 正减正 (A - B)
    if (!neg1 && !neg2) {
        if (cmp >= 0) {  // A ≥ B
           return BigInteger(unsigned_sub(abs1, abs2));
       } else {          // A < B
           return BigInteger("-" + unsigned_sub(abs2, abs1));
       }
    }
    // 2. 正减负 (A - (-B) = A + B)
    else if (!neg1 && neg2) {
        return BigInteger(unsigned_add(abs1, abs2));
    }
    // 3. 负减正 (-A - B = -(A + B))
    else if (neg1 && !neg2) {
        std::string sum = unsigned_add(abs1, abs2);
        if (sum == "0") return BigInteger("0");
        return BigInteger("-" + sum);
    }
    // 4. 负减负 (-A - (-B) = B - A)
    else { // 两个负数
        if (cmp == 0) {         // 绝对值相等
            return BigInteger("0");
        } 
        else if (cmp > 0) {     // |A| > |B| = -(A - B)
            std::string res = unsigned_sub(abs1, abs2);
            if (res == "0") return BigInteger("0");
            return BigInteger("-" + res);
        } 
        else {                  // |B| > |A| = B - A
            return BigInteger(unsigned_sub(abs2, abs1));
        }
    }
}

/**
 * 双目运算，二者相乘
 * @param this lvalue @param args rvalue
 * @return 相乘结果
*/
const BigInteger BigInteger::operator* (const BigInteger& args) const {
    // 提取操作数
    std::string num1 = this->arr;
    std::string num2 = args.arr;
    
    // 检查乘数为0的情况
    if (num1 == "0" || num2 == "0") {
        return BigInteger("0");
    }
    
    // 确定结果符号
    bool neg1 = (num1[0] == '-');
    bool neg2 = (num2[0] == '-');
    bool resultNegative = (neg1 != neg2);
    
    // 提取绝对值部分
    std::string abs1 = neg1 ? num1.substr(1) : num1;
    std::string abs2 = neg2 ? num2.substr(1) : num2;
    
    // 使用竖式乘法实现大数乘法
    int len1 = abs1.size();
    int len2 = abs2.size();
    int totalLen = len1 + len2;
    std::vector<int> result(totalLen, 0);  // 足够存储结果的数组
    
    // 反向遍历：从个位开始
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            // 当前位乘积
            int product = (abs1[i] - '0') * (abs2[j] - '0');
            // 计算结果位置
            int pos1 = i + j;
            int pos2 = i + j + 1;
            // 加上之前的结果
            int sum = product + result[pos2];
            
            // 存储结果
            result[pos2] = sum % 10;
            result[pos1] += sum / 10;
        }
    }
    
    // 转换为字符串
    std::string resultStr;
    for (int i = 0; i < totalLen; i++) {
        // 跳过前导零
        if (resultStr.empty() && result[i] == 0) continue;
        resultStr += (result[i] + '0');
    }
    
    // 处理全零结果
    if (resultStr.empty()) {
        return BigInteger("0");
    }
    
    // 添加符号
    if (resultNegative) {
        resultStr = "-" + resultStr;
    }
    
    return BigInteger(resultStr);
}

/**
 * 双目运算，二者相除
 * @param this lvalue @param args rvalue
 * @return 相除结果
*/
const BigInteger BigInteger::operator/ (const BigInteger& divisor) const {
    if (divisor.arr == "0" || divisor.arr == "-0") {
        throw std::invalid_argument("Division by zero"); //不能整除0则抛出异常
    }
    if (this->arr == "0" || this->arr == "-0") {
        return BigInteger("0"); //被除数为0则结果为0
    }
    
    bool dividendNeg = (this->arr[0] == '-');
    bool divisorNeg = (divisor.arr[0] == '-');
    bool resultNeg = (dividendNeg != divisorNeg); //判断结果是否为负数
    
    std::string absDividend = dividendNeg ? this->arr.substr(1) : this->arr;
    std::string absDivisor = divisorNeg ? divisor.arr.substr(1) : divisor.arr;
    
    if (absDividend.length() < absDivisor.length() || 
        (absDividend.length() == absDivisor.length() && absDividend < absDivisor)) {
        return BigInteger("0");
    }
    
    std::string quotient;
    std::string current;
    int idx = 0; // 当前处理位置
    
    // 跳过被除数前导零
    while (idx < absDividend.length() && absDividend[idx] == '0') idx++;
    if (idx == absDividend.length()) return BigInteger("0");
    
    for (; idx < absDividend.length(); idx++) {
        // 追加当前数字
        current += absDividend[idx];
        
        // 移除当前段的前导零 (保证current非空)
        size_t pos = current.find_first_not_of('0');
        if (pos == std::string::npos) {
            current = "";
        } else if (pos != 0) {
            current = current.substr(pos);
        }
        
        // 当前段为空时视为0
        if (current.empty()) {
            quotient += "0";
            continue;
        }
        
        // 比较当前段与除数
        if (current.length() < absDivisor.length() || 
            (current.length() == absDivisor.length() && current < absDivisor)) {
            quotient += "0";
            continue;
        }
        
        // 二分法快速试商
        int digit = 0;
        int low = 1, high = 9;
        while (low <= high) {
            int mid = (low + high) / 2;
            std::string midStr = std::string(1, '0' + mid);
            BigInteger multiple = BigInteger(absDivisor) * BigInteger(midStr);
            
            if (multiple.arr.size() < current.length() || 
               (multiple.arr.size() == current.length() && multiple.arr <= current)) {
                digit = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        quotient += ('0' + digit);
        std::string prod = (BigInteger(absDivisor) * BigInteger(std::string(1, '0'+digit))).arr;
        BigInteger remainder = BigInteger(current) - BigInteger(prod);
        current = remainder.arr;
        if (current == "0") current = ""; // 归零处理
    }
    
    // 处理前导零
    if (quotient.empty()) quotient = "0";
    else {
        size_t pos = quotient.find_first_not_of('0');
        if (pos == std::string::npos) quotient = "0";
        else if (pos != 0) quotient = quotient.substr(pos);
    }
    
    if (resultNeg && quotient != "0") {
        quotient = "-" + quotient;
    }
    
    return BigInteger(quotient);
}

/**
 * 双目运算，右边对左边做取余操作
 * @param this lvalue @param args rvalue
 * @return 取余结果
*/
const BigInteger BigInteger::operator% (const BigInteger& divisor) const {
    // 计算商
    BigInteger quotient = *this / divisor;
    
    // 计算余数 = 被除数 - 除数 * 商
    BigInteger remainder = *this - divisor * quotient;
    
    // 修正余数符号
    bool thisNeg = (arr[0] == '-');
    if (remainder != BigInteger("0")) {
        // 确保余数符号与被除数相同
        if (thisNeg && remainder.arr[0] != '-') {
            remainder.arr = "-" + remainder.arr;
        } 
        else if (!thisNeg && remainder.arr[0] == '-') {
            // 如果被除数为正，余数为负，加上除数绝对值修正
            remainder = remainder + divisor.abs();
        }
    }
    
    return remainder;
}

// 前置递增 (++a)
BigInteger& BigInteger::operator++() {
    // 加1
    *this = *this + BigInteger("1");
    return *this;
}

// 后置递增 (a++)
BigInteger BigInteger::operator++(int) {
    // 保存原始值
    BigInteger temp = *this;
    // 加1
    *this = *this + BigInteger("1");
    // 返回原值
    return temp;
}

// 前置递减 (--a)
BigInteger& BigInteger::operator--() {
    // 加1
    *this = *this - BigInteger("1");
    return *this;
}

// 后置递减 (a--)
BigInteger BigInteger::operator--(int) {
    // 保存原始值
    BigInteger temp = *this;
    // 加1
    *this = *this - BigInteger("1");
    // 返回原值
    return temp;
}

/**
 * 相当于*this = *this + other
*/
BigInteger& BigInteger::operator+=(const BigInteger& other) {
    *this = *this + other;
    return *this;
}

/**
 * 相当于*this = *this - other
*/
BigInteger& BigInteger::operator-=(const BigInteger& other) {
    *this = *this - other;
    return *this;
}

/**
 * 相当于*this = *this * other
*/
BigInteger& BigInteger::operator*=(const BigInteger& other) {
    *this = *this * other;
    return *this;
}

/**
 * 相当于*this = *this / other
*/
BigInteger& BigInteger::operator/=(const BigInteger& other) {
    *this = *this / other;
    return *this;
}

/**
 * 相当于*this = *this % other
*/
BigInteger& BigInteger::operator%=(const BigInteger& other) {
    *this = *this % other;
    return *this;
}